package myTest.linckedList;

public class LinkedListUtil {
	public static Node reverse(Node head) {
		Node p0 = head;
		if (p0 == null)// 没有 节点
			return null;

		Node p1 = p0.next;
		if (p1 == null)// 一个节点
			return p0;

		// 1个以上
		p0.next = null;
		Node p2 = p1.next;
		while (p2 != null) {
			p1.next = p0;
			p0 = p1;
			p1 = p2;
			p2 = p2.next;
		}
		p1.next = p0;
		return p1;
	}

	public static Node isIntersected(Node n1, Node n2) {
		if (n1 == null || n2 == null)
			return null;
		if (n1 == n2)
			return n1;
		Node p1 = n1;
		Node p2 = n2;
		int l1 = 0;
		int l2 = 0;
		int len = 0;

		while (p1.next != null) {
			l1++;
			p1 = p1.next;
		}

		while (p2.next != null) {
			l2++;
			p2 = p2.next;
		}

		if (p2 != p1)// 最后节点不一样,说明不相交
			return null;

		// 如果相交

		if (l1 >= l2) {
			len = l1 - l2;
			p1 = n1;
			p2 = n2;
		} else {
			len = l2 - l1;
			p1 = n2;
			p2 = n1;
		}
		while (len-- != 0) {// 长的先遍历掉多出的部分
			p1 = p1.next;
		}
		while (p1 != p2) {
			p1 = p1.next;
			p2 = p2.next;
		}
		return p1;
	}

	public static boolean isCycle(final Node head) {
		if (head == null)
			return false;

		Node p1 = head;
		Node p2 = head;

		while (true) {
			p1 = p1.next;
			if (p1 == null)
				return false;

			p2 = p2.next;
			if (p2 == null)
				return false;

			p2 = p2.next;
			if (p2 == null)
				return false;

			if (p2 == p1)
				return true;
		}
	}

	public static void display(Node head) {
		while (head != null) {
			System.out.println(head);
			head = head.next;
		}
	}
}
